⟸ pàgina anterior ⟸
Exercici 6 (Tasca 2).
(regular languages, homomorphism, minimization of DFAs)

L’homomorfisme d’un llenguatge regular és regular

  1. Construïu de forma explícita el DFA mínim per al llenguatge \sigma(L), on

    1. L=\{axbya\mid x,y\in\{a,b\}^*\} i \sigma és l’homomorfisme definit per \sigma(a)=aa i \sigma(b)=ba.
    2. L=\{axbyc\mid x,y\in\{a,b,c\}^*\} i \sigma és l’homomorfisme definit per \sigma(a)=ab, \sigma(b)=b i \sigma(c)=\lambda.
    3. L=\{xbcya\mid x,y\in\{a,b,c\}^*\} i \sigma és l’homomorfisme definit per \sigma(a)=bbb, \sigma(b)=a i \sigma(c)=\lambda.

    Calculeu el DFA mínim que reconeix L. A partir d’aquest DFA, construïu el \lambda-NFA A que reconeix el llenguatge \sigma(L). Finalment, fent servir la construcció de subconjunts, feu A determinista i minimitzeu el DFA obtingut.

    Recordeu que, donat un DFA A i un morfisme \sigma, és possible construir un NFA que reconegui el llenguatge \sigma(L(A)) transformant cada transició \ \stackrel{a}{\to}\ a A en \ \stackrel{\sigma(a)}{\to}\ en un autòmat estès i convertint cada transició estesa en un \lambda-NFA tot afegint nous estats.

  2. Donat un DFA A com a entrada, quin és el cost de calcular un DFA per a \sigma(L(A))? Produeix un DFA la construcció per obtenir un NFA que reconegui \sigma(L(A))?

  3. Funciona la construcció per obtenir un NFA que reconegui \sigma(L(A)) en cas que A sigui un NFA? En altres paraules, si es transforma cada transició \ \stackrel{a}{\to}\ d’un NFA A en una transició estesa \ \stackrel{\sigma(a)}{\to}\ i després es converteix en un \lambda-NFA tot afegint nous estats, s’obté un \lambda-NFA correcte per a \sigma(L(A))?